package com.test.daily.leetcode.y2021.m10.day1019;

/**
 * WordDictionary
 *
 * @author Tom on 2021/10/19
 */
public class Code02_WordDictionary {
}

class Trie02{

    private Trie02[] children;
    private boolean end;

    public Trie02(){
      end = false;
      children = new Trie02[26];
    }

    public boolean dfs(Trie02 root, int index, String word){
        if(index == word.length()){
            return root.isEnd();
        }
        char ch = word.charAt(index);
        if(Character.isLetter(ch)){
            int childIndex = ch - 'a';
            Trie02 child = root.getChildren()[childIndex];
            if(child != null && dfs(child, index + 1, word)){
                return true;
            }
        } else {
            for(int i = 0; i < 26; i++){
                Trie02 child = root.getChildren()[i];
                if(child!= null && dfs(child, index + 1, word)){
                    return true;
                }
            }
        }
        return false;
    }
    public void insert(String word){
       char[] chs = word.toCharArray();
       Trie02 node = this;
       for(int i = 0; i < chs.length; i++){
           int childIndex = chs[i] - 'a';
           if(node.getChildren()[childIndex] == null){
               node.getChildren()[childIndex] = new Trie02();
           }
           node = node.getChildren()[childIndex];
       }
       node.end = true;
    }

    public Trie02[] getChildren(){
        return this.children;
    }

    public boolean isEnd(){
        return end;
    }
}
